﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using KaroInterface;

namespace Emerald
{
    public static class MiniMax
    {
        #region Members


        private const int MaxDepth = 2;
        private static EColor aiColor;
        private static Stopwatch _sw = new Stopwatch();

        #endregion

        #region Methods


        public static IAction MiniMaxDecision(GameState g,EColor AIColor)
        {
            IAction act = new Action();

            aiColor = AIColor;
            _sw.Reset();
            _sw.Start();
            GameState[] states = OrderMoves(g.NextPossibleStates(1),false);

            int min = int.MaxValue;
            int max = int.MinValue;
            int count = states.Count(t => t != null);
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                //int maxValue = MinValue(gx, 1, null);
                int maxValue = MinValueWithAlphaBetaPruning(gx, 1, max, int.MaxValue);
                //int maxValue = -AlphaBeta(gx, 0, int.MinValue+1, int.MaxValue-1,false);
                //int maxValue2 = MaxValueRec(gx, MaxDepth-1);

                Application.DoEvents();
#if DEBUG
                //Console.WriteLine("Base State: " + i + " Value: "+maxValue + " Vslur3: NAN");
#endif
                if (maxValue > max)
                {
#if DEBUG
                    Console.WriteLine("New best move on: " + i);
#endif
                    max = maxValue;
                    act = gx.CreationMove;
                }
                if (maxValue < min)
                {
#if DEBUG
                    Console.WriteLine("New worst move on: " + i);
#endif
                    min = maxValue;
                }
            }
            _sw.Stop();
#if DEBUG
            Console.WriteLine("Time: " + _sw.ElapsedMilliseconds);
#endif

            return act;
        }

        public static int MaxValueRec(GameState g, int depth)
        {
            if (depth == MaxDepth)
            {
                int gameStateValue = EvaluateGameState(g);
                return gameStateValue;
            }

            int value = int.MinValue;
            GameState[] states = g.NextPossibleStates(depth);
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                value = Math.Max(value, -MaxValueRec(gx, depth + 1));
            }
            return value;
        }

        public static int MaxValue(GameState g, int depth, Node<int> node)
        {
            if (depth == MaxDepth)
            {
                int gameStateValue = EvaluateGameState(g);
                //node.AddChild(gameStateValue);
                return gameStateValue;
            }

            //Node<int> child = node.AddChild();

            int value = int.MinValue;
            GameState[] states = g.NextPossibleStates(depth);
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                value = Math.Max(value, MinValue(gx, depth + 1, null));
            }

            //child.Value = value;

            return value;
        }

        public static int MinValue(GameState g, int depth, Node<int> node)
        {
            if (depth == MaxDepth)
            {
                int gameStateValue = EvaluateGameState(g);
                //node.AddChild(gameStateValue);
                return gameStateValue;
            }

            //Node<int> child = node.AddChild();

            int value = int.MaxValue;
            GameState[] states = g.NextPossibleStates(depth);
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                value = Math.Min(value, MaxValue(gx, depth + 1, null));
            }

            //child.Value = value;

            return value;
        }

        public static int MaxValueWithAlphaBetaPruning(GameState g, int depth, int alpha, int beta)
        {
            if (depth == MaxDepth || g.IsWonByPlayer() != null)
            {
                int gameStateValue = EvaluateGameState(g);
                return gameStateValue;
            }

            GameState[] states = OrderMoves(g.NextPossibleStates(depth),false);

            int value = int.MinValue;
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                value = Math.Max(value, MinValueWithAlphaBetaPruning(gx, depth + 1, alpha, beta));
                if (value >= beta)
                {
                    //Console.WriteLine("{3} Pruned at element {0}, a={1}, b={2}", i, alpha, beta, "Max");
                    break;
                }

                if (value > alpha)
                {
                    alpha = value;

                    //Console.WriteLine("alpha is now: " + alpha);
                }
            }

            return value;
        }

        public static int MinValueWithAlphaBetaPruning(GameState g, int depth, int alpha, int beta)
        {
            if (depth == MaxDepth || g.IsWonByPlayer() != null)
            {
                int gameStateValue = EvaluateGameState(g);
                return gameStateValue;
            }

            GameState[] states = OrderMoves(g.NextPossibleStates(depth),true);
            int value = int.MaxValue;
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                value = Math.Min(value, MaxValueWithAlphaBetaPruning(gx, depth + 1, alpha, beta));
                if (value <= alpha)
                {
                    //Console.WriteLine("{3} Pruned at element {0}, a={1}, b={2}", i, alpha, beta, "Min");
                    break;
                }

                if (value < beta)
                {
                    beta = value;
                    //Console.WriteLine("beta is now: "+beta);
                }
            }

            return value;
        }

        /*
         * function alphabeta(node, depth, α, β)         
                (* β represents previous player best choice - doesn't want it if α would worsen it *)
                if  depth = 0 or node is a terminal node
                    return the heuristic value of node
                for each child of node
                    α := max(α, -alphabeta(child, depth-1, -β, -α))     
                    (* use symmetry, -β becomes subsequently pruned α *)
                    if β≤α
                        break                             (* Beta cut-off *)
                return α

            (* Initial call *)
            alphabeta(origin, depth, -infinity, +infinity)
         */

        public static int AlphaBeta(GameState g, int depth, int alpha, int beta, bool max)
        {
            if (depth == MaxDepth)
            {
                int evalValue = EvaluateGameState(g);

                return evalValue;
            }
            if (TranspositionTable.Instance.Contains(g, MaxDepth - depth + 1))
                return TranspositionTable.Instance.GetValue(g);

            //GameState[] states = g.NextPossibleStates();
            GameState[] states = OrderMoves(g.NextPossibleStates(depth),max);
            int result = 0;
            for (int i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                    break;

                result = -AlphaBeta(gx, depth + 1, -beta, -alpha, !max);
                gx.Depth = MaxDepth - depth;
                TranspositionTable.Instance.AddGamestate(gx);
                alpha = Math.Max(alpha, result);
                if (beta <= alpha)
                {
#if DEBUG
                    //Console.WriteLine("{3} Pruned at element {0}, a={1}, b={2}", i, alpha, beta,max);
#endif
                    break;
                }
            }

            return alpha;
        }



        public static int EvaluateGameState(GameState g)
        {
            //Stopwatch sw = Stopwatch.StartNew();
            // we start at zero!!
            int score = 0;


            // TODO : think of a scoring mechanism / scoring rules
            //  - # of marked pieces
            //  - # size of grouped (marked) pieces
            //  - # of possible movable tiles
            //  - # of possible locations to move a tile to
            //  - # etc .. think of more :D


            // # of marked pieces in the winning state(horizontal,vertical or diagonal):

            // pseudo code

            // first check if we have a winner
            EColor? winner = g.IsWonByPlayer();
            if (winner != null)
            {
                if (winner.Value == aiColor)
                    return 10000000;
                if (winner.Value == aiColor.Opposite())
                    return -10000000;
            }

            // count the number of marked pieces and check whether these are in a row/grouped
            //  - increase score
            //    - do we have grouped pieces? increase score as well
            int v = 0;


            Tile[] markedtiles = g.Board.BoardArray.GetMarkedTiles(g.ColorToPlay);

            for (short i = 0; i < markedtiles.Length; i++)
            {
                if (markedtiles[i] == null) break;

                v += 100;
            }

            markedtiles = g.Board.BoardArray.GetMarkedTiles(g.ColorToPlay.Opposite());

            for (short i = 0; i < markedtiles.Length; i++)
            {
                if (markedtiles[i] == null) break;

                v -= 75;
            }


            int temp = evalutateMarkedTilesForColor(g, g.ColorToPlay);
            temp -= evalutateMarkedTilesForColor(g, g.ColorToPlay.Opposite());

            v += temp;


            //sw.Stop();
            //Console.WriteLine(sw.Elapsed);)
            return v;
        }

        private static GameState[] OrderMoves(GameState[] states, bool ascending)
        {
            int i;
            //evaluate the gamestates
            for (i = 0; i < states.Length; i++)
            {
                GameState gx = states[i];
                if (gx == null)
                {
                    break;
                }
                gx.EvalValue = EvaluateGameState(gx);
            }
            // Move Ordering:
            //    states = MoveOrdering.MergeSort(states,ascending);
            //    return states;
            Array.Sort(states, 0, i, new GameStateSorter(ascending));
            return states;
            //if(ascending)
            //return states.TakeWhile(gs => gs != null).OrderBy(gs => gs.EvalValue).ToArray();
            //return states.TakeWhile(gs => gs != null).OrderByDescending(gs => gs.EvalValue).ToArray();
        }

        private class GameStateSorter : IComparer<GameState>
        {
            private readonly bool _ascending;

            public GameStateSorter(bool @ascending)
            {
                _ascending = ascending;
            }

            public int Compare(GameState x, GameState y)
            {
                return (x.EvalValue - y.EvalValue) * (_ascending ? +1 : -1);
            }
        }


        private static int evalutateMarkedTilesForColor(GameState g, EColor c)
        {
            Tile[] markedTiles = g.Board.BoardArray.GetMarkedTiles(c);
            int v = 0;
            for (int i = 0; i < markedTiles.Length; i++)
            {
                Tile markedTile = markedTiles[i];
                if (markedTile == null)
                    break;
                v += BoardEvaluator(g.Board.BoardArray, markedTile, c);
            }
            return v;
        }

        internal static int BoardEvaluator(BoardArray boardArray, Tile tile, EColor color)
        {
            // base case
            if (tile == null || tile.Piece == null) return 0;

            int temp = 0;
            int v = 0;
            int c = 0;
            for (sbyte y = -1; y < 1; y++)
            {
                for (sbyte x = -1; x < 1 && c < 4; x++, c++)
                {
                    temp = BoardEvaluator(boardArray, tile, x, y, color);

                    // 2 means this tile ıs empty, so increase the score a little
                    if (temp == 2) temp += 10;

                    v += temp;

                    if (x == 0 && y == 0) { c--; continue; }

                    temp = BoardEvaluator(boardArray, tile, (sbyte)(-x), (sbyte)(-y), color);

                    // 2 means this tile ıs empty, so increase the score a little
                    if (temp == 2) temp += 10;

                    v += temp;
                }
            }

            return v;
        }

        internal static int BoardEvaluator(BoardArray boardArray, Tile tile, sbyte dX, sbyte dY, EColor color)
        {
            // base case
            if (tile == null || tile.Piece == null)
                return 0;

            float multiplier = 5.0f;

            if (boardArray.IsFilledTile(tile.Location, dX, dY) &&
                boardArray[(byte)(tile.Location.X + dX), (byte)(tile.Location.Y + dY)].Piece.Color == color &&
                boardArray[(byte)(tile.Location.X + dX), (byte)(tile.Location.Y + dY)].Piece.State == EState.Marked)
            {
                int valueOfCurrentTile = 4; //(boardArray[(byte)(tile.Location.X + dX), (byte)(tile.Location.Y + dY)].Piece.State == EState.Marked ? 4 : 1);
                if (dX == 0 && dY == 0)
                    return valueOfCurrentTile;

                int temp = BoardEvaluator(boardArray,
                                   boardArray[(byte)(tile.Location.X + dX),
                                   (byte)(tile.Location.Y + dY)],
                                   dX,
                                   dY,
                                   color);

                return valueOfCurrentTile * (int)(temp * multiplier);

            }

            // return 2 in case of an empty tile; thıs way we can use this value to increase
            // the value even more. We cant ıncrease it here because this value is directly used
            // ın a multiplication
            if (boardArray.IsTile(tile.Location, dX, dY) &&
                boardArray[(byte)(tile.Location.X + dX), (byte)(tile.Location.Y + dY)].Piece == null)
                return 2;

            // do NOT return a 0; Zeros are BAD in multiplications
            return 1;
        }

        #endregion
    }

    public class Tree<T> where T : IComparable<T>
    {
        public Node<T> Root { get; private set; }

        public Tree(T rootValue)
        {
            Root = new Node<T> { Value = rootValue };
        }

        public Tree()
            : this(default(T))
        { }

        public override string ToString()
        {
            return this.Root.ToString();
        }
    }

    public class Node<T> where T : IComparable<T>
    {
        private const int INDENTWIDTH = 4;

        public T Value { get; set; }
        public List<Node<T>> Children { get; private set; }
        public bool IsLeaf { get { return Children.Count == 0; } }
        public bool IsParentOfLeafsOnly { get { return false == IsLeaf && Children.All(n => n.IsLeaf); } }

        public Node()
        {
            Value = default(T);
            Children = new List<Node<T>>();
        }

        public Node<T> AddChild(T value)
        {
            Node<T> c = new Node<T> { Value = value };
            Children.Add(c);
            return c;
        }

        public Node<T> AddChild()
        {
            Node<T> c = new Node<T> { Value = default(T) };
            Children.Add(c);
            return c;
        }

        public override string ToString()
        {
            return "how about NO!"; toString(0).TrimEnd();
        }

        private string toString(int indents)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < indents * INDENTWIDTH; i++)
            {
                sb.Append(" ");
            }
            sb.AppendLine(string.Format("{0}", Value));

#if !true
            if (this.IsParentOfLeafsOnly)
            {
                Dictionary<T, int> freq = new Dictionary<T, int>();
                foreach (Node<T> child in Children)
                {
                    if (freq.ContainsKey(child.Value))
                        freq[child.Value]++;
                    else
                        freq.Add(child.Value, 1);
                }

                string format = "{0," + ((indents + 2) * INDENTWIDTH + 1) + "} ({1,2}x)";
                foreach (KeyValuePair<T, int> keyValuePair in freq.OrderByDescending(f => f.Key))
                {
                    sb.AppendLine(string.Format(format, keyValuePair.Key, keyValuePair.Value));
                }
            }
            else
#endif
            {
                foreach (Node<T> child in Children)
                {
                    sb.Append(child.toString(indents + 1));
                }
            }
            return sb.ToString();
        }
    }
}
